1. Field of the Invention
The present invention relates to the field of telecommunications. More particularly, the present invention relates to a system and a method for multicast conferencing and online discussion groups.
2. Description of the Related Art
Recently, there is an increasing interest in designing and implementing multicast routing protocols suitable for conferencing or online chat/discussion groups. For example, see S. Deering, Host extensions for IP multicasting, RFC 1112, May, 1988; D. Waitzman et al., Distance vector multicast routing protocol, RFC 1075, 1988; B. M. Waxman, Routing of multipoint connections, IEEE Journal on Selected Areas in Communications, Vol. 6-9, pp. 1617-1622, December 1988, S. Deering et al., Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems, pp. 85-111, May 1990; M. Doar et al., How bad is naive multicasting, Proceedings of the IEEE INFOCOM, pp. 82-89, 1993; and J. Moy, Multicast routing extensions for OSPF, Comm. of the ACM, Vol. 37-8, pp. 61-66, August 1994, each of which is incorporated by reference herein.
An important step m the development of multicast routing protocols has been the deployment of a multicast version of the distance vector routing protocol (DVMRP) over the Multicast Backbone (MBone). For example, see D. Waitzman et al., supra; and H. Eriksson, Mbone: the multicast backbone, Comm. of the ACM, pp. 54-60, August 1994, which is incorporated by reference herein. A multicast version of a link-state routing protocol (MOSPF) has also been developed. For example, see J. Moy, supra. These particular multicast schemes were designed for densely distributed group members. Furthermore, these multicast schemes were designed for supporting separate source based trees for each sender. More recently, protocols for sparsely distributed group members have also been proposed. For example, see A. J. Ballardie et al., Core based trees, Proceedings of the ACM SIGCOMM, 1993; and S. Deering et al., An architecture for wide-area multicast routing, Proceedings of the ACM SIGCOMM, August, pp. 126-135, August 1994, each of which is incorporated by reference herein.
A key characteristic of conferencing or online chat/discussion groups is that there are typically several speakers sending messages at various times during a discussion session and any listener may decide to contribute to the discussion. Additionally, speakers (senders) are also listeners (receivers) of messages. Currently, discussion groups, such as news groups and other talk groups, are implemented by all traffic being sent to a central site. The traffic is then rebroadcast from the central site to all participants of a group using well-known unicast techniques. A higher bandwidth than what is presently available will be needed for discussion groups configured in this manner so that video and audio information can be sent along with textual information and so that such groups can operate in real-time. As the number of this type of discussion groups increases, currently available multicasting protocols will not suffice.
Two types of trees have generally been used for multicast routing: source-based trees and shared trees. In particular, the previously mentioned DVMRP protocol sets up source-based trees, while core-based tree (CBT) protocols develop shared trees. For example, see A. J. Ballardie et al., supra. The advantages and disadvantages of these two types of multicast spanning trees are well-known. For example, source-based trees are best suited for minimum delay type applications, but have a serious scaling problem because each router in a source-based tree maintains state information for every source-group pair. A core-based tree protocol sets up a single multicast tree having one or more cores for an entire group. Additionally, a core address is used in data packets for multicasting routing, and no distinction is made between senders and receivers. The scaling problem associated with source-based trees is overcome by shared trees, but it is argued in the literature that each link of a shared tree suffers from traffic concentration for certain applications. Another disadvantage of core-based trees is that members join and leave the shared tree in a distributed manner which usually causes the tree to drift away from an optimal configuration during the course of a given multicast session.
The Protocol Independent Multicasting (PIM) approach has been taken by the internet community. See S. Deering et al., supra. The PIM protocol approach has a major drawback caused by separating senders from receivers. In fact, this protocol provides no simple way for converting a sender into a receiver in an existing multicast tree. Consequently, the PIM protocol approach has drawbacks with certain applications, such as conferencing and chat groups, in which senders and receivers interchange roles often during a session.
Steiner trees have been suggested at various times for use in multicasting. For example, see V. P. Kompella et al., Multicasting for multimedia applications, Proc. IEEE INFOCOM, pp. 2078-2085, 1992, Ph.D. Thesis; L. Wei et al., A comparison of multicast trees and algorithms, CS. Dept. Tech. Report, Univ. of Southern California, September 1993; and H. F. Salama et al., Comparison of Multicast Routing Algorithms for high-speed networks, IBM Tech. Report, September 1994, each of which is incorporated by reference herein. The problem of determining a Steiner tree for a multicast network, that is, the minimum weight tree spanning a given subset D of a graph W, is known as the Steiner problem for networks. The problem has been well-studied and is known to be an NP-complete problem. For example, see R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, 1972, which is incorporated by reference herein. Nevertheless, reasonable heuristics exist for finding an approximate solution in polynomial time. For example, the Takahashi Matsuyama heuristic, disclosed by H. Takahashi et al., An approximate solution for the Steiner problem in graphs, Math. Japonica, vol. 6, pp. 573-577, 1980, incorporated by reference herein, has been effectively used for determining approximate Steiner trees, such as the approximate Steiner trees disclosed by S. Hakimi, Steiners problem in graphs and its applications, Networks, vol. 1, pp. 113-133, 1971, incorporated by reference herein. Another heuristic for finding an approximate solution is disclosed by V. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs, Int. J. Math. Educ. Sci. Tech., vol. 14, pp. 15-23, 1983, incorporated by reference herein. Some work has also been done in computing constrained Steiner trees in a centralized manner. For example, see V. P. Kompella et al., supra. Distributed versions of the same algorithm are presented by V. P. Kompella et al., Multicast routing for multimedia communications, IEEE/ACM Trans. on Networking, vol. 1-3, pp. 286-292, June 1993, incorporated by reference herein. Nevertheless, Steiner trees have generally been deemed to be unsuitable for multicasting because the maximal delay is longer than the maximal delay for shortest path trees, and it is often argued that traffic is concentrated on the Steiner spanning tree links whereas traffic is more distributed in shortest path-type trees.
What is needed is a multicast routing protocol that defines how a multicast session is initiated and terminated, and how members to the session join and leave a multicast group. Additionally, a multicast routing protocol is needed that periodically recomputes a near-optimal Steiner tree for a multicast group that changes dynamically, and periodically allows switching from an old Steiner tree to a new Steiner tree. Further, a multicast protocol is needed that provides a high probability of delivery during transitions from an old tree to the newly computed tree, even when membership to a multicast session changes rapidly, for example, such as in a mobile environment. Further still, a multicast protocol is needed that provides inter-domain multicasting with fault tolerance features.